// @algorithm @lc id=526 lang=cpp 
// @title beautiful-arrangement


// #define print(...)
// @test(2)=2
// @test(1)=1
#define USE_DP
#ifdef USE_DP // 动态规划
class Solution {
public:
    int countArrangement(int n) {
        vector<int> dp(1<<n);
        dp[0] = 1;
        for(int used=1; used<(1<<n); used++){
            int j = __builtin_popcount(used);
            for(int u=used; u>0; u&=u-1){
                int i = __builtin_ctz(u) + 1;
                if(j%i && i%j) continue;
                dp[used] += dp[ used - (1<<(i-1)) ];
            }
        }
        return dp[(1<<n)-1];
    }
};
#else // 回溯
class Solution {
public:
    int countArrangement(int n) {
        vector<vector<int>> beautiesOf(n+1);
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i%j && j%i) continue;
                beautiesOf[i].emplace_back(j);
            }
        }

        int ans = 0;
        bitset<16> used;
        function<void(int)> dfs = [&](int i){
            if(i == n+1){
                ans++;
                return;
            }
            for(auto b : beautiesOf[i]){
                if(used[b]) continue;
                if(i%b && b%i) continue;
                used.flip(b);
                dfs(i+1);
                used.flip(b);
            }
        };
        dfs(1);
        return ans;
    }
};
#endif